package com.itcast.demo.tokkit;

/**
 * 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
 *
 * @author zheng.zhang
 */
public class JumpTest {
    public static void main(String[] args) {
        JumpTest test = new JumpTest();
        int num = test.jumpFloor(4);
        System.out.println(num);
    }

    /**
     * 输入: 4
     * 返回: 5
     *
     * 思路: f(1)->1    f(2)->2    f(n) = f(n-1) + f(n-2)
     * @param target 目标台阶数
     * @return 总共到达台阶的次数
     */
    public int jumpFloor(int target) {
        if (target < 0) {
            return -1;
        }
        if (target <= 2) {
            return target;
        }
        int result = 0;
        int preNum = 2;
        int prePreNum = 1;
        for (int i = 3; i <= target; i++) {
            result = preNum + prePreNum;
            prePreNum = preNum;
            preNum = result;
        }
        return result;
    }
}
